Atari Mega Archive 1/Atari Mega Archive - Volume 1.iso/lists/gem/l_1199/1149

Internet Message Format | 1994-08-27 | 9.9 KB

Subject: ShortCuts - TSR code
Date: Mon, 01 Aug 1994 18:38:38 +1000
From: Warwick Allison <[e-mail]>
Precedence: bulk


I have written the main body of the tree-based storage scheme
for APP_DEFS.SYS.

It's very fast, and quite small.  It is included below.

I haven't written the actual TSR/cookie stuff, just the actual storage
and retrieval mechanism (ie. the hard part).  This code could even be used
outside a TSR - in the app itself, and it would be the fastest way to
retrieve attributes.  (In that case, I would add an extra line to filter
out the settings of attributes for applications other than the loader).

I hope this demonstrates the utility of the app_defs.sys format which I have
proposed.  It contains sample look-up code, which gives the following
result:

Given an app_defs.sys file (note, no " " near ":"):

*.quit.key:^Q
*.quit.name:Quit
*.new.key:^N
*.new.name:New
*.open.key:^O
*.open.name:Open...
*.close.key:^C
*.close.name:Close
*.selectall.key:^A
atariworks.*selectall.key:+^A
gumby.*.selectall.key:+^B
*.confirmexit.flag: no
calamus.confirmexit.flag: yes

It match the following attribute/values:

mydraw.quit.key:^Q
atariworks.quit.name:Quit
atariworks.selectall.key:+^A
atariworks.wp.selectall.key:+^A
atariworks.db.selectall.key:+^A
atariworks.ss.selectall.key:+^A
gumby.foo.selectall.key:+^B
gumby.selectall.key:^A


/* APP_DEFS.SYS TSR
**
** Author:  Warwick Allison ([e-mail])
**          (Copyright)
**
** Reads APP_DEFS.SYS file, installs a cookie providing access to the
** defaults via a simple interface.
**
** Defaults are stored in a highly efficient tree, allowing attribute
** look-up in O(length-of-attribute) time, regardless of number of
** defaults actually stored.  Storage cost of the tree may be LESS THAN
** the total size of the app_defs file (since common prefixes are shared).
**
** eg.
**     a.b.c:1
**     a.b.d:2
**
** is stored as:
**
**     a.b
**        .c:1
**        .d:2
**
** Storage cost is 20 bytes for each segment (text between '.'), plus
** space of actual non-'.' text.
**
** So, approximately 50 bytes average per attribute.  100 global
** attibutes, plus 500 application-specific attributes = 3Kbytes.
** This is very cheap.
**
** main() loads the app_defs.sys file.  Access is then via:
**
**    char* get_default_text(char* attribute)
**
** STATUS:
**   For evaluation - TSR linkage not implemented.
**   main() includes TEST code that allows interactive examination
**   of the system.
**
**   Spaces on either side of the ":" in app_defs.sys file, are considered
**   part of the attribute or value.
*/

#include <stdio.h>
#include <string.h>

#define MAXPATTERN 128
#define MAXVALUE 128
#define WILDCARD '*'
#define APPDEFS "app_defs.sys" /* ie. in root drive */

void test();

typedef struct NodeRec {
    struct NodeRec* next;
    char* match_segment;
    char* value;
    struct NodeRec* subnode;
    int priority;
} Node;

void dump(Node* node, int indent)
/* Show tree as indented list (for debugging) */
{
    static char* space="                         ";
#define maxspace 25

    if (node) {
        if (node->value) {
            printf("%s%s %s\n",
                space+maxspace-indent,
                node->match_segment,
                node->value
            );
        } else {
            printf("%s%s\n",space+maxspace-indent,node->match_segment);
        }

        dump(node->subnode,indent+1);
        dump(node->next,indent);
    }
}

Node* new_node()
{
    return (Node*)malloc(sizeof(Node));
}

char* submatch(char* a, char* b)
/* Match a against b, up to '.' or '\0' in a.
** Return next segment (in a) after '.' or on '\0', or 0 if no match.
*/
{
    while (*a==*b && *b && *a && *a!='.') {
        a++; b++;
    }

    if (*b) return 0; /* No match */
    if (*a==*b) return a; /* Match - at end */
    if (*a=='.') return a+1; /* Match - at . */
    return 0; /* How did this happen? */
}

char* submatch_wild(char* a, char* b, int skip_dots)
/* Match a against b, up to '.' or '\0' in a.
** Return next segment (in a) after '.' or on '\0', or 0 if no match.
** Honour wildcard '*' in b.  Allow wildcards to consume up to
** the given number of dots.
**
** (the requirement of skip_dots increases the complexity of this function)
*/
{
    while (1) { /* This loop removes a simple tail recursion */

        if (*b==WILDCARD) {
            char* try=0;
            if (*a && *a!='.') try=submatch_wild(a+1,b,skip_dots);
            if (try) return try;
            if (*a=='.' && skip_dots) try=submatch_wild(a+1,b,skip_dots-1);
            if (try) return try;
            try=submatch_wild(a,b+1,skip_dots);
            return try;
        }

        if (*a=='.' || !*a) {
            /* End of a */
            if (*b) return 0;
            else return *a ? a+1 : a;
        } else {
            if (*a!=*b) {
                /* Match failed */
                return 0;
            } else {
                /* Match so-far */
                a++;b++; /* This could be coded as tail recursion */
            }
        }
    }
}

char* cut_segment(char** pattern)
/* Move *pattern forward to begining of next segment (after '.'),
** return copy of segment moved over.
*/
{
    char* start=*pattern;
    while (**pattern && **pattern!='.') {
        (*pattern)++;
    }
    if (**pattern) {
        **pattern=0;
        (*pattern)++;
    }
    return strdup(start);
}


Node* root=0;

void add_mapping(Node** node, char* pattern, char* value, int priority)
/* Add given pattern->value mapping, with the given priority,
** to the tree at the given node.
*/
{
    if (*node) {
        char* end_pat=submatch(pattern,(*node)->match_segment);
        if (end_pat) {
            /* Matches here */
            if (*end_pat) {
                /* Still more to match */
                add_mapping(&(*node)->subnode, end_pat, value, priority);
            } else {
                /* End of pattern - store value here */
                if ((*node)->value) {
                    /* XXX Overriding (could generate message */
                    free((*node)->value);
                }
                (*node)->value=strdup(value);
                (*node)->priority=priority;
            }
        } else {
            /* No match */
            add_mapping(&(*node)->next, pattern, value, priority);
        }
    } else {
        /* New node */

        *node=new_node();
        (*node)->next=0;
        (*node)->match_segment=cut_segment(&pattern);
        (*node)->subnode=0;

        if (*pattern) {
            /* More to go */
            (*node)->value=0;
            (*node)->priority=0;
            add_mapping(&(*node)->subnode, pattern, value, priority);
        } else {
            /* Leaf node */
            (*node)->value=strdup(value);
            (*node)->priority=priority;
        }
    }
}

int count_dots(char* str)
{
    int n;
    for (n=0; *str; str++) {
        if (*str=='.') n++;
    }
    return n;
}

char* look_up(Node* node, char* pattern, int* priority)
/* Lookup the given pattern, return the value with the highest
** priority in the given tree.  Set *priority.
**
** (simplistic algorithm used for matching dots)
*/
{
    if (node) {
        char* best_result=0;
        int best_priority=-1;
        char* local_result=0;
        int local_priority=0;
        int dots=count_dots(pattern);

#   define UPDATE_BEST \
    if (local_result && local_priority>best_priority) {     \
        best_priority=local_priority; \
        best_result=local_result; \
    }

        while (dots>=0) {
            char* end_pat=submatch_wild(pattern,node->match_segment,dots);

            if (end_pat) {
                /* Matches here */
                if (*end_pat) {
                    /* Still more to match */
                    local_result=look_up(node->subnode, end_pat, &local_priority);
                    UPDATE_BEST
                } else {
                    /* End of pattern - retrieve value from here */
                    /* (perhaps 0) */
                    local_result=node->value;
                    local_priority=node->priority;
                    UPDATE_BEST
                }
            }

            dots--;
        }

        /* Try siblings */
        local_result=look_up(node->next, pattern, &local_priority);
        UPDATE_BEST

#   undef UPDATE_BEST

        *priority=best_priority;
        return best_result;
    } else {
        return 0;
    }
}


main()
{
    FILE* file=fopen(APPDEFS,"r");

    if (file) {
        char pattern[MAXPATTERN];
        char value[MAXVALUE];
        int priority=1;

        while (1) {
            char first=fgetc(file);
            ungetc(first,file);

            if (first=='#') {
                /* comment */
                fscanf(file,"%*[^:\n]");
            } else {
                if (fscanf(file,"%[^:\n]:%[^\n]\n",pattern,value)!=2)
                    break; /* END */

                add_mapping(&root,pattern,value,priority);
                priority++;
            }
        }

        fclose(file);
    }

    /* Install look-up function */

    /* Terminate, stay resident */

    test();
}




/* The functions below would be exported via a cookie interface */

char* get_default_text(char* attribute)
{
    int priority;
    return look_up(root,attribute,&priority);
}

char* get_default_number(char* attribute, int* intvalue)
{
    char* value=get_default_text(attribute);
    if (value) {
        /* Something smarter than this, eg. hex numbers */
        *intvalue=atoi(value);
    }
    return value;
}

char* get_default_flag(char* attribute, int* boolvalue)
{
    char* value=get_default_text(attribute);
    if (value) {
        /* No error check:  assume that if it isn't yes, it is no */
        static char* yes[]={"yes","on","true","oui","ja","1",0};
        char** y;
        for (y=yes; *y && strcmp(value,*y); y++)
            ;
        *boolvalue=!!*y;
    }
    return value;
}

char* get_default_scancode(char* attribute, int* scancode)
{
    char* value=get_default_text(attribute);
    if (value) {
        /* ... */
    }
    return value;
}

/* etc. */


/* Potentially, these could also be added, if generally useful... */

void add_default(char* attribute_pattern, char* value);
/* Trivial - calls add_mapping() with next priority */

int save();
/* This would have to output in priority order (line order of original file),
** and should preserve comments.
**
** One solution would be to re-read the
** original file, copy across comments, lookup each attribute (without using
** wildcard search), copy across attribute and new value, mark as output,
** then traverse tree outputting other attributes.  Difficult to preserve
** order in which post-load attributes were defined.
*/





void test()
{
    char pattern[MAXPATTERN];
    char value[MAXVALUE];

/* TEST: submatch_wild (if you're interested in playing with matches)
    int dots;
    while (EOF!=scanf("%s %s %d",pattern,value,&dots)) {
        char* result;
        result=submatch_wild(pattern,value,dots);
        if (result) {
            printf("Yes, leaving \"%s\"\n",result);
        } else {
            printf("No match\n");
        }
    }
    exit(0);
*/

    /* TEST:  dump */
    dump(root,0);

    printf("\n[Enter patterns to look up:]\n\n");

    /* TEST:  look things up */
    while (gets(pattern)) {
        char* value;
        int priority;
        if (value=look_up(root,pattern,&priority)) {
            printf("%s:%s\n",pattern,value);
        } else {
            printf("%s NOT FOUND\n",pattern);
        }
    }
}